/*
 * @lc app=leetcode.cn id=1562 lang=cpp
 *
 * [1562] 查找大小为 M 的最新分组
 */

// @lc code=start
class Union
{
public:
    vector<int> data, size, count;
    Union(int n) : data(n + 1), size(n + 1), count(n + 2, 0)
    {
        for (int i = 0; i <= n; i++)
        {
            data[i] = i;
            size[i] = 1;
        }
        count[1] = n + 1;
    }
    int find(int x)
    {
        if (data[x] == x)
            return x;
        return (data[x] = find(data[x]));
    }
    void merge(int x, int y)
    {
        int rx = find(x), ry = find(y);
        if (rx == ry)
            return;
        if (size[rx] < size[ry])
        {
            swap(rx, ry);
        }
        data[rx] = ry;
        count[size[rx]]--;
        count[size[ry]]--;
        size[ry] += size[rx];
        count[size[ry]]++;
    }
};

class Solution
{
public:
    int findLatestStep(vector<int> &arr, int m)
    {
        int n = arr.size(), ans = -1;
        Union uf(n);
        for (int i = 0; i < n; i++)
        {
            uf.merge(arr[i], arr[i] - 1);
            if (uf.count[m + 1])
                ans = i + 1;
        }
        return ans;
    }
};
// @lc code=end
